//组合总和2
class Solution {
public:
    vector<vector<int>>res;
    vector<int>tmp;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
    {
        sort(candidates.begin(),candidates.end());
        dfs(candidates,target,0,0);
        return res;
    }
    void dfs(vector<int>&candidates,int target,int curi,int sum)
    {
        if(sum==target)
        {
            res.push_back(tmp);
            return;
        }
        if(sum>target) return;
        unordered_set<int>hash;
        for(int i=curi;i<candidates.size();i++)
        {
            if(hash.find(candidates[i])!=hash.end()) continue;
            hash.insert(candidates[i]);
            tmp.push_back(candidates[i]);
            dfs(candidates,target,i+1,sum+candidates[i]);
            tmp.pop_back();
        }
    }
};